/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/07
 */
package CodingTest.AC20190307;
/**
 * 链接：https://www.nowcoder.com/questionTerminal/d732267e73ce4918b61d9e3d0ddd9182
 来源：牛客网

 小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力
 输入描述:

 每个输入包含一个测试用例。
 每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。


 输出描述:

 输出一个数表示小Q第一天最多能吃多少块巧克力。
 示例1
 输入

 3 7
 输出

 4


 思路：使用二分法减少复杂度，但通过率只有80%，
   解法二为网上解法，通过率为100%
 */

import java.util.Scanner;

public class eatChocolate {
    static int day;
    static int total;
    public int eatChocolate(int day,int total){
        int high = total;
        int low = 1;
        while(high>low){
            int middle = (low+high)/2;
                int sum = sum(middle,day);
                if(sum == total){
                    return middle;
                }else if(sum>total){
                    high = middle-1;
                }else{
                    low = middle+1;
                }

        }
        return high;
    }
    public int sum(int middle,int day){
        int sum = 0;
        for(int i = 0;i<day;i++){
            sum+=middle;
            middle = (int)Math.ceil((double)middle / 2);
        }
        return sum;
    }


    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        day = sc.nextInt();
//        total = sc.nextInt();
        eatChocolate ec = new eatChocolate();
        System.out.println(ec.eatChocolate(100,382));

    }

}
//    --------------------------------------------------------------------------------------------
//    解法二：
//static int day;
//    static int total;
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        day = in.nextInt();
//        total = in.nextInt();
//        if(day == 1) {
//            System.out.println(total);
//            return;
//        }
//        int low = 1;
//        int high = total;
//        int mid = 0;
//        while(low <= high) {
//            mid = low + (high - low) / 2;
//            int sum = sum(mid);
//            if(sum > total) {
//                high = mid - 1;
//            } else if(sum < total) {
//                low = mid + 1;
//            } else {
//                high = mid;
//                break;
//            }
//        }
//        System.out.println(high);
//    }
//    private static int sum(int mid) {
//        int sum = 0;
//        for(int i = 0; i < day; i++) {
//            sum = sum + mid;
//            mid = (int)Math.ceil((double)mid / 2);
//        }
//        return sum;
//    }

